#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <semaphore.h>
#include "memory.h"
#include "get_memory.h"
extern int info[MAX_L];
extern int sum;
extern Buddy* p_tree;
extern void* base;
extern sem_t g_sem;

// get_memory() function implementation
void*
get_memory(int size)
{
sem_wait(&g_sem);
    int one =1;                 // for bit shifting, to implement 2^n
    int need = size + sizeof(mem_header_t);
	printf("User request for %d space\n", need);
	printf("The size of the whole memory is %d space\n", sum);
		
    int l, i, j;
    l = 0;          // to mark the level of suitable size.
	
	if(need>sum) {
		printf("Can't get more than memory limit\n");
sem_post(&g_sem);
		return NULL;
	}	
	

	
    while (need <= sum/(one<<l)) {
        if (need <= sum/(one<<(l+1)))
            l++;
        else
            break;
    }

	
    if (info[l] == 0)    // if no space for allocation, return NULL.
	{   
	    printf("The number of available blocks is %d\n", info[l]);
		printf("There is no memory block avialble. \n");
sem_post(&g_sem);
        return NULL;
	}

    // search for an available tree node
    int level_head = (one<<l) - 1;      // to find the offset of the first node on this level.
    int level_end = (one<<(l+1)) - 2;   // to find the offset of the last node on this level.
	  
	  
    Buddy* tree = p_tree;
	mem_header_t *hd = NULL;

    for (j = 0, i = level_head; i <= level_end; j++, i++ ) {    // j counter the index on the level
	    
        if (tree[i].p == NULL) {        // find the first available tree node, and add info of the block, malloc it
            tree[i].p = (void *) (&base[j*sum/(level_head+1)]);        // record the address info in 
			info[l]--;
			
            // operate the info in parent nodes, and parent level info.
            int a = l;
            int tmp_level = level_head+1;  //2^l
		
                while (a > 0) {
					
					//if left node & parent node is NULL, build the parent and point it to left child
                    if (j%2 == 0 && tree[tmp_level/2 -1 + j/2].p == NULL) {   
          
                        tree[tmp_level/2 -1 + j/2].p = tree[i].p;				
                        tree[tmp_level/2 -1 + j/2].left = &tree[i];
                        tree[tmp_level/2 -1 + j/2].right = NULL;
										
                        a--;
                        tmp_level /= 2;
						i /= 2;
						
				        info[a]--; // modify the parent level availability record	
                        j=j/2;						
                    }
                    else {  // if parent node is not NULL, meaning right not used, or left released
                        if (j%2 == 0 && tree[tmp_level/2 -1 + j/2].p != NULL) {
                            tree[tmp_level/2 -1 + j/2].left = &tree[i];
							printf("ReBuild the left child\n");
						}
                        else {
                            tree[tmp_level/2 -1 + j/2].right = &tree[i];
							printf("Build the right child\n"); 
							printf("tree [%d]'s right child is now tree [%d] \n",tmp_level/2 -1 + j/2 , i);

						}
						j=j/2;	
                        break;      // do not need to recursively go up to build parents.
                    }
				
                }

             break;   
		

        }
		
    }
sem_post(&g_sem);
	// write the block header, and return the pointer for user
	hd = (mem_header_t *) tree[i].p;
	hd->size = size;
	hd->canary = (long) CANARY_OK;
	return (void *)&(hd[1]);
	
}


